/* 720. 词典中最长的单词 */
/**
 * @param {string[]} words
 * @return {string}
 */
/* 
    定义[符合要求的单词]如下
    ·空字串是符合要求的单词
    ·在符合要求的单词末尾添加一个字母，得到的新单词是符合要求的单词
*/
var longestWord = function (words) {
    /* 
        单词长度不一样的时候，按照升序排列 ，
        如果单词长度相同，则按照字典序降序排列
    */
    words.sort((a, b) => {
        if (a.length !== b.length) {
            return a.length - b.length
        } else {
            /* 
                用本地特定的顺序来比较两个字符串
                stringObject.localeCompare(target)

                var str 
                str.sort((a,b) => a.localeCompare(b))
            */
            return b.localeCompare(a)
        }
    })
    let longest = ""
    let candidates = new Set()
    candidates.add("")
    const n = words.length
    for (let i = 0; i < n; i++) {
        const word = words[i]
        if (candidates.has(word.slice(0, word.length - 1))) {
            candidates.add(word)
            longest = word
        }
    }

    return longest
};

/* 字典树 */
class Node {
    constructor() {
        this.children = {}
        this.isEnd = false
    }
}
class Trie {
    constructor() {
        this.children = new Node()
        this.isEnd = false
    }

    insert (word) {
        let node = this
        for (let i = 0; i < word.length; i++) {
            const ch = word[i]
            const index = ch.charCodeAt() - 'a'.charCodeAt()
            if (!node.children[index]) {
                node.children[index] = new Node()
            }
            node = node.children[index]
        }
        node.isEnd = true
    }

    search (word) {
        let node = this
        for (let i = 0; i < word.length; i++) {
            const ch = word[i]
            const index = ch.charCodeAt() - 'a'.charCodeAt()
            if (!node.children[index] || !node.children[index].isEnd) {
                return false
            }

            node = node.children[index]
        }

        return node && node.isEnd
    }
}

var longestWord = function (words) {
    const trie = new Trie()
    for (const word of words) {
        trie.insert(word)
    }
    let longest = ""
    for (const word of words) {
        if (trie.search(word)) {
            if (word.length > longest.length || (word.length === longest.length && word.localeCompare(longest) < 0)) {
                longest = word
            }
        }
    }
    return longest
}
longestWord(["a", "banana", "app", "appl", "ap", "apply", "apple"])